/*
** Copyright (C) 2009 Joshua Brent Marsh <joshua@icub3d.com>
**  
** This file is part of icub3d-adt
**
** icub3d-adt is free software; you can redistribute it and/or modify
** it under the terms of the GNU General Public License as published by
** the Free Software Foundation; either version 3 of the License, or
** (at your option) any later version.
**  
** This program is distributed in the hope that it will be useful,
** but WITHOUT ANY WARRANTY; without even the implied warranty of
** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
** GNU General Public License for more details.
**  
** You should have received a copy of the GNU General Public License
** along with this program; if not, write to the Free Software
** Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
**  
*/

/* $Id: set.c 14 2009-10-15 04:47:03Z joshua@icub3d.com $ */

#ifdef HAVE_CONFIG_H
#include <config.h>
#endif

#include <stdlib.h>
#include <assert.h>

#include "set.h"
#include "btree.h"

int 
set_subset (Set *s1, Set *s2)
{
  SetTraverser trav;
  void *cur;

  assert (s1 != NULL);
  assert (s2 != NULL);
  assert (s1->comp == s2->comp);

  set_traverser_init (&trav, s1);
  while ((cur = set_traverser_next (&trav)) != NULL)
    {
      /* all the items in s1 would be in s2 if they were a sub-set. 
	 If one doesn't exist, return 0. */
      if (!set_exists (s2, cur))
	return 0;
    }
  
  return 1;
}

int 
set_equal (Set *s1, Set *s2)
{
  assert (s1 != NULL);
  assert (s2 != NULL);
  assert (s1->comp == s2->comp);

  /* If they aren't the same size, they can't be equal. */
  if (set_size (s1) != set_size (s2))
    return 0;

  /* If they are the same size and s1 is a sub-set of s2, then they must
     be equal. */
  return set_subset (s1, s2);
}

int
set_distinct (Set *s1, Set *s2)
{
  SetTraverser trav;
  void *cur;

  assert (s1 != NULL);
  assert (s2 != NULL);
  assert (s1->comp == s2->comp);

  set_traverser_init (&trav, s1);
  while ((cur = set_traverser_next (&trav)) != NULL)
    {
      /* None of the items in s1 would be in s2 if they are distinct.
	 If one does exist, return 0. */
      if (set_exists (s2, cur))
	return 0;
    }
  
  return 1;

}

Set * 
set_union (Set *s1, Set *s2)
{
  SetTraverser trav;
  Set *nset;
  void *cur;

  assert (s1 != NULL);
  assert (s2 != NULL);
  assert (s1->comp == s2->comp);

  /* Our new set. */
  nset = set_create (s1->comp);
  if (nset == NULL)
    return NULL;

  /* Add all the items in set1 to the new set. */
  set_traverser_init (&trav, s1);
  while ((cur = set_traverser_next (&trav)) != NULL)
    {
      if (set_add (nset, cur) == NULL)
	{
	  set_destroy (nset, NULL);
	  return NULL;
	}
    }

  /* Add all the items in set2 to the new set. NOTE: We don't
     clean up dups, s1 will have precedence. */
  set_traverser_init (&trav, s2);
  while ((cur = set_traverser_next (&trav)) != NULL)
    {
      if (set_add (nset, cur) == NULL)
	{
	  set_destroy (nset, NULL);
	  return NULL;
	}
    }
  
  return nset;
}

Set * 
set_intersect (Set *s1, Set *s2)
{
  SetTraverser trav;
  Set *nset;
  void *cur;

  assert (s1 != NULL);
  assert (s2 != NULL);
  assert (s1->comp == s2->comp);

  /* Our new set. */
  nset = set_create (s1->comp);
  if (nset == NULL)
    return NULL;

  set_traverser_init (&trav, s1);
  while ((cur = set_traverser_next (&trav)) != NULL)
    {
      /* If an item in s1 is in s2, then it belongs in the intersecting set. */
      if (set_exists (s2, cur))
	{
	  if (set_add (nset, cur) == NULL)
	    {
	      set_destroy (nset, NULL);
	      return NULL;
	    }
	}
    }

  return nset;
}

Set * 
set_difference (Set *s1, Set *s2)
{
  SetTraverser trav;
  Set *nset;
  void *cur;

  assert (s1 != NULL);
  assert (s2 != NULL);
  assert (s1->comp == s2->comp);

  nset = set_create (s1->comp);
  if (nset == NULL)
    return NULL;

  set_traverser_init (&trav, s1);
  while ((cur = set_traverser_next (&trav)) != NULL)
    {
      /* If an item in s1 isn't in s2, then it will be in the difference set. */
      if (!set_exists (s2, cur))
	{
	  if (set_add (nset, cur) == NULL)
	    {
	      set_destroy (nset, NULL);
	      return NULL;
	    }
	}
    }

  return nset;
}
